package 栈;

import java.util.Stack;

// https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
public class _150_逆波兰表达式求值 {
    public static int evalRPN(String[] tokens) {
        Stack<Integer> numbers = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String string = tokens[i];

            try {
                int num = Integer.parseInt(string);
                numbers.push(num);
            } catch (Exception e) {
                int num1 = numbers.pop();
                int num2 = numbers.pop();
                if (string.equals("+")) {
                    numbers.push(num1+num2);
                } else if (string.equals("-")) {
                    numbers.push(num2-num1);
                } else if (string.equals("*")) {
                    numbers.push(num1*num2);
                } else if (string.equals("/")) {
                    numbers.push(num2/num1);
                }
            }
        }
        return numbers.pop();
    }

    public static int evalRPN2(String[] tokens) {
        int length = tokens.length;
        int[] numbers = new int[length];
        int k = -1;
        for (int i = 0; i < length; i++) {
            String string = tokens[i];

            try {
                int num = Integer.parseInt(string);
                numbers[++k] = num;
            } catch (Exception e) {
                if (string.equals("+")) {
                    numbers[k-1] += numbers[k];
                    k--;
                } else if (string.equals("-")) {
                    numbers[k-1] -= numbers[k];
                    k--;
                } else if (string.equals("*")) {
                    numbers[k-1] *= numbers[k];
                    k--;
                } else if (string.equals("/")) {
                    numbers[k-1] /= numbers[k];
                    k--;
                }
            }
        }
        return numbers[0];
    }

    public static void main(String[] args) {
        System.out.println(evalRPN2(new String[]{"2", "1", "+", "3", "*"}));
        System.out.println(evalRPN2(new String[]{"4", "13", "5", "/", "+"}));
        System.out.println(evalRPN2(new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}));
    }
}
